首页 > 试题广场 >

对称的二叉树

[编程题]对称的二叉树

热度指数：478560 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
例如：下面这棵二叉树是对称的

下面这棵二叉树不对称。

数据范围：节点数满足 $0 \le n \le 1000$ ，节点上的值满足 $|val| \le 1000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

备注：

你可以用递归和迭代两种方法解决这个问题

示例1

输入

{1,2,2,3,4,4,3}

输出

true

示例2

输入

{8,6,9,5,7,7,5}

输出

false

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

推荐

Ron

/*思路：首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同
* 左子树的右子树和右子树的左子树相同即可，采用递归
* 非递归也可，采用栈或队列存取各级子树根节点
*/
public class Solution {
	boolean isSymmetrical(TreeNode pRoot)
	{
		if(pRoot == null){
			return true;
		}
		return comRoot(pRoot.left, pRoot.right);
	}
	private boolean comRoot(TreeNode left, TreeNode right) {
		// TODO Auto-generated method stub
		if(left == null) return right==null;
		if(right == null) return false;
		if(left.val != right.val) return false;
		return comRoot(left.right, right.left) && comRoot(left.left, right.right);
	}
}

编辑于 2015-08-18 23:10:28 回复(46)

Python 3

JianYue

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return bool布尔型
#
class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        if pRoot is None:
            return True
        left, right = pRoot.left, pRoot.right
        lt, rt = [left], [right]
        while len(lt) > 0 and len(rt) > 0:
            one = lt.pop()
            two = rt.pop()
            if one is None and two is None:
                continue
            if one is None&nbs***bsp;two is None:
                return False
            if one.val != two.val:
                return False
            o_l = one.left
            one_r = one.right
            lt.insert(-1, o_l)
            lt.insert(-1, one_r)
            t_l = two.left
            t_r = two.right
            rt.insert(-1, t_r)
            rt.insert(-1, t_l)
        return True

发表于 2022-09-13 21:33:09 回复(0)

Python 3

xuyjbug404

你们的代码怎么效率这么快啊，

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return bool布尔型
#
class Solution:
    def inorder(self, node1, node2):
        if not node1 and not node2:
            return True
        elif not node1&nbs***bsp;not node2:
            return False
        elif node1.val != node2.val:
            return False
        
        if self.inorder(node1.left, node2.right):
            return self.inorder(node1.right,node2.left)
    
        return False

    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        # write code here
        if not pRoot:
            return True
    
        return self.inorder(pRoot.left,pRoot.right)

发表于 2022-08-22 16:48:12 回复(0)

Python 3

前端_小白菜

难道不可以用中序遍历之后，比较列表的正逆序吗

发表于 2022-08-05 17:08:46 回复(0)

Python 3

东方佑

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return bool布尔型
#
class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:

        if pRoot:
            return self.levelOrder(pRoot)
        else:
            return True

    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        self.val_list=[]
        h=root
#         print(h)
        l=self.get_next_h(h)
        
        while l:
            l=self.get_next_hh(l)
            if "0" in self.val_list:
                return False
#         print(self.val_list)
        print(self.val_list)

        if "0" not in self.val_list:
            return True
        else:
            return False

        

    def get_next_h(self,x):
        self.val_list.append("1")
        return [x.left,x.right]

    def get_next_hh(self,x):

        l_r_list=[]
        l_r_list_val=[]
        val_one=[]
        for one in x: 
            if one:
                val_one.append(str(one.val))
                if one.left:

                    l_r_list.append(one.left)
                    l_r_list_val.append(1)
                
                else:
                    l_r_list.append(None)
                    l_r_list_val.append(0)
                if one.right:
                    l_r_list.append(one.right)
                    l_r_list_val.append(1)
                else:
                    l_r_list.append(None)
                    l_r_list_val.append(0)
        print(val_one,l_r_list_val)
        
        if val_one:
            b_v=val_one==val_one[::-1]
            b_b=l_r_list_val==l_r_list_val[::-1]
            if len(val_one)==1:
                
                self.val_list.append("0")
            
            elif b_v and b_b:
                self.val_list.append("1")
            else:
                self.val_list.append("0")

        
        return l_r_list

发表于 2022-07-12 17:45:05 回复(0)

Python 3

Vivimore

class Solution:
    def recurssion(self, root1, root2):
        if not root1 and not root2:
            return True
        if not root1 or not root2 or root1.val != root2.val:
            return False
        return self.recurssion(root1.left, root2.right) and self.recurssion(root1.right, root2.left)
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        return self.recurssion(pRoot, pRoot)

发表于 2022-05-06 14:29:28 回复(0)

Python 3

英俊的嘟教授上岸了

中序遍历方法
class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        if not pRoot:
            return True
        midOrder_list = []
        midOrder_list = self.midOrder(midOrder_list, pRoot)
        long = len(midOrder_list)
        if long % 2 == 0:
            return False
        else:
            mid = long // 2
            if midOrder_list[0:mid] == midOrder_list[mid + 1:long][::-1]:
                return True
            return False

    def midOrder(self, midOrder_list: list, pRoot: TreeNode) -> list:
        if not pRoot:
            return
        self.midOrder(midOrder_list, pRoot.left)
        if not pRoot.left and pRoot.right:
            midOrder_list.append([])
        midOrder_list.append(pRoot.val)
        if not pRoot.right and pRoot.left:
            midOrder_list.append([])
        self.midOrder(midOrder_list, pRoot.right)
        return midOrder_list

发表于 2022-05-06 11:07:32 回复(0)

Python 3

付付吖

class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        # write code here
        if not pRoot:
            return True
#         if not pRoot.left and not pRoot.right:
#             return True
        quene =[pRoot]
        while quene:
            c = []
            for i in range(len(quene)):
                node = quene.pop(0)
                if node:
                    c.append(node.val)
                    quene.append(node.left)
                    quene.append(node.right)
                else:
                    c.append(0)
            if c != c[::-1]:
                return False
            if node != pRoot and len(c) % 2 != 0:
                return False
        return True

发表于 2022-03-13 20:03:13 回复(0)

Python 3

kinter1

class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        import operator
        temp1 = []
        temp2 = []
        def left2right(proot, temp1):
            if proot is None:
                temp1.append(1001)
                return 
            temp1.append(proot.val)
            left2right(proot.left, temp1)
            left2right(proot.right, temp1)
        def right2left(proot, temp2):
            if proot is None:
                temp2.append(1001)
                return 
            temp2.append(proot.val)
            right2left(proot.right, temp2)
            right2left(proot.left, temp2)
        left2right(pRoot, temp1)
        right2left(pRoot, temp2)
    #    print(temp1, temp2)
        if operator.eq(temp1, temp2):
            return True
        else:
            return False

发表于 2022-03-05 21:05:27 回复(0)

Python 3

Gelivabilities

方法1：拆成左右子树两个参数，用新函数递归

class Solution:
    '''法1：递归但不构造虚拟结点，改成多参数递归即可'''
    def isSym(self, p_left, p_right):
        if not p_left and not p_right: return True
        if not p_left&nbs***bsp;not p_right: return False
        if p_left.val != p_right.val: return False
        return self.isSym(p_left.left, p_right.right) and self.isSym(p_left.right, p_right.left)
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        return True if not pRoot else self.isSym(pRoot.left, pRoot.right)

方法2：构造对称轴虚拟结点，用原函数递归

class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        '''法2：构造对称轴结点递归'''
        if not pRoot: return True
        if not pRoot.left and not pRoot.right: return True
        if not pRoot.left or not pRoot.right: return False
        if pRoot.left.val != pRoot.right.val: return False
        virtual_node_1, virtual_node_2 = TreeNode(0), TreeNode(0)
        virtual_node_1.left, virtual_node_1.right = pRoot.left.left, pRoot.right.right
        virtual_node_2.left, virtual_node_2.right = pRoot.left.right, pRoot.right.left
        return self.isSymmetrical(virtual_node_1) and self.isSymmetrical(virtual_node_2)

方法3：用队列

class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:)
        '''法1：队列'''
        if not pRoot: return True
        if not pRoot.left and not pRoot.right: return True
        if not pRoot.left&nbs***bsp;not pRoot.right: return False
        queue_l, queue_r = [pRoot.left], [pRoot.right]
        while queue_l != [] and queue_r != []:
            if queue_l[0].val != queue_r[0].val: return False
            l_pop, r_pop = queue_l.pop(0), queue_r.pop(0)
            if l_pop.left:
                if not r_pop.right: return False
                queue_l.append(l_pop.left)
                queue_r.append(r_pop.right)
            if l_pop.right:
                if not r_pop.left:  return False
                queue_l.append(l_pop.right)
                queue_r.append(r_pop.left)
        return queue_l == [] and queue_r == []

发表于 2022-02-27 20:06:40 回复(0)

Python 3

菜鸡尼欧

简单的递归

class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        # write code here
        if not pRoot:
            return True
        return self.helper(pRoot.left, pRoot.right)
    
    def helper(self, left, right):
        if not left and not right:
            return True
        if not left and right:
            return False
        if left and not right:
            return False
        return left.val == right.val and self.helper(left.left, right.right) and self.helper(left.right, right.left)

发表于 2022-02-12 12:16:11 回复(0)

Python 3

Joy_9

class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        def sys(r,l):
            if r and l and r.val==l.val:
                if sys(l.right,r.left) and sys(l.left,r.right):
                    return True
                else:
                    return False
            elif not r and not l:
                return True
        return sys(pRoot,pRoot)

发表于 2022-01-09 01:36:36 回复(0)

Python 3

闲良

class Solution:
def isSymmetrical(self , pRoot: TreeNode) -> bool:
# write code here
if pRoot is None: return True
return self.sametree(pRoot.left, self.symone(pRoot.right))

def symone(self, pRoot: TreeNode) -> TreeNode:
if pRoot and (pRoot.left is not None or pRoot.right is not None):
temp = self.symone(pRoot.left)
pRoot.left = self.symone(pRoot.right)
pRoot.right = temp
return pRoot

def sametree(self, p1, p2) -> bool:
if p1 is None:
if p2 is None:
return True
else:
return False
elif p2 is None:
return False
else:
if p1.val != p2.val:
return False
else:
return self.sametree(p1.left, p2.left) and self.sametree(p1.right, p2.right)

发表于 2022-01-04 21:44:06 回复(0)

Python 3

牛客925293305号

py递归

class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        # write code here
        if not pRoot:
            return True
        return self.check(pRoot.left, pRoot.right)
    def check(self, r1, r2):
        if (not r1) and (not r2):
            return True
        elif r1 and r2:
            if r1.val != r2.val:
                return False
            return self.check(r1.left, r2.right) and self.check(r1.right, r2.left)
        return False

发表于 2021-12-03 18:35:28 回复(0)

Python 3

JSFaner

class Solution:
    def isSymmetrical(self, pRoot):
        def recur(left,right):
            if not left and not right: return True
            if not left&nbs***bsp;not right: return False
            if left.val != right.val: return False
            return recur(left.left,right.right) and recur(left.right,right.left)
        if not pRoot: return True
        return recur(pRoot.left, pRoot.right)

发表于 2021-11-21 18:26:14 回复(0)

Python 3

牛客927268134号

## 先翻转左子树再判断左右子树是否相等，空间O(1)
class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        # write code here
        if not pRoot&nbs***bsp;(not pRoot.left and not pRoot.right):
            return True
        if pRoot.left and pRoot.right:
            ## Mirror left
            arr = [pRoot.left]
            while arr:
                top = arr[0]
                arr = arr[1:]
                tmp = top.left
                top.left = top.right
                top.right = tmp
                if top.left:
                    arr.append(top.left)
                if top.right:
                    arr.append(top.right)
            arr = [pRoot.left]
            arr2 = [pRoot.right]
            while arr:
                top = arr[0]
                top2 = arr2[0]
                if (
                    top.val != top2.val&nbs***bsp;                   (bool(top.left is None) ^ bool(top2.left is None))&nbs***bsp;                   (bool(top.right is None) ^ bool(top2.right is None))&nbs***bsp;                   (top.left is not None and top.left.val != top2.left.val)&nbs***bsp;                   (top.right is not None and top.right.val != top2.right.val)
                ):
                    return False
                else:
                    arr = arr[1:]
                    arr2 = arr2[1:]
                    if top.left:
                        arr.append(top.left)
                        arr2.append(top2.left)
                    if top.right:
                        arr.append(top.right)
                        arr2.append(top2.right)
            return True
        else:
            return False

发表于 2021-11-19 09:27:50 回复(0)

Python 3

tantantansq

class Solution:
    def isSym(self,left,right):
        if left==None and right==None:
            return True
        if left==None&nbs***bsp;right==None&nbs***bsp;left.val!=right.val:
            return False
        return self.isSym(left.left, right.right) and self.isSym(left.right, right.left)
    
    def isSymmetrical(self, pRoot):
        # write code here
        if pRoot==None:
            return True
        return self.isSym(pRoot.left,pRoot.right)

发表于 2021-08-09 01:04:43 回复(0)

Python 3

牛客549486156号

class Solution:
def core(self,pRoot1,pRoot2):
if not pRoot1 or not pRoot2:
return pRoot1 == pRoot2
return pRoot1.val == pRoot2.val and \
self.core(pRoot1.left,pRoot2.right) and \
self.core(pRoot1.right,pRoot2.left)

def isSymmetrical(self, pRoot):
# write code here
if not pRoot:
return True
return self.core(pRoot.left,pRoot.right)

发表于 2021-07-24 00:25:55 回复(0)